/*************************************************************************
 * File Name:    Insert_Interval.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/17 21:22:06
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Insert Interval
 |
 | Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
 |
 | You may assume that the intervals were initially sorted according to their start times.
 |
 | Example 1:
 | Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 |
 | Example 2:
 | Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
 |
 | This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval)
    {
        vector<Interval> ans;
        
        bool passed = false;
        for (size_t i = 0; i < intervals.size(); ++i) {
            if (intervals[i].start <= newInterval.start && intervals[i].end >= newInterval.start) {
                newInterval.start = intervals[i].start;
                newInterval.end = max(newInterval.end, intervals[i].end);
            } else if (intervals[i].start <= newInterval.end && intervals[i].end >= newInterval.end) {
                newInterval.start = min(intervals[i].start, newInterval.start);
                newInterval.end = intervals[i].end;
            } else if (intervals[i].end < newInterval.start) {
                ans.push_back(intervals[i]);
            } else if (intervals[i].start > newInterval.end) {
                if (!passed) ans.push_back(newInterval);
                passed = true;
                ans.push_back(intervals[i]);
            }
        }
        if (!passed) ans.push_back(newInterval);
        return ans;
    }
};

int
main(int argc, char *argv[])
{
    Solution sol;

    vector<Interval> intervals;

    intervals.push_back(Interval(1,2));
    intervals.push_back(Interval(3,5));
    intervals.push_back(Interval(6,7));
    intervals.push_back(Interval(8,10));
    intervals.push_back(Interval(12,16));

    Interval newInterval(4,9);

    vector<Interval> ans = sol.insert(intervals, newInterval);

    for (size_t i = 0; i < ans.size(); ++i) {
        cout << ans[i].start << " " << ans[i].end << endl;
    }

    return 0;
}
